from collections import defaultdict

class 场景战术系统:
    def __init__(self):
        self.图 = defaultdict(list)
        self.入度 = defaultdict(int)
        self.节点集合 = set()
        self.边到步骤 = {}
        self.边到权重 = {}
        self.节点优先级 = {}
        
    def 添加连接(self, 源设备, 目标设备, 边权重=0, 步骤描述=None):
        """添加一个从源设备到目标设备的连接，包含边权重"""
        if 步骤描述 is None:
            步骤描述 = f"{源设备} -> {目标设备}"
            
        self.图[源设备].append(目标设备)
        self.入度[目标设备] += 1
        self.节点集合.add(源设备)
        self.节点集合.add(目标设备)
        self.边到步骤[(源设备, 目标设备)] = 步骤描述
        self.边到权重[(源设备, 目标设备)] = 边权重
        
        if 源设备 not in self.节点优先级:
            self.节点优先级[源设备] = 0
        if 目标设备 not in self.节点优先级:
            self.节点优先级[目标设备] = 0
    
    def 设置节点优先级(self, 设备, 优先级):
        """设置单个节点的优先级"""
        self.节点优先级[设备] = 优先级
        
    def 生成攻击步骤(self):
        """使用改进的算法生成考虑节点优先级的攻击步骤序列"""
        当前入度 = self.入度.copy()
        
        已处理的节点 = set()
        已处理的边 = set()
        步骤序列 = []
        
        while len(已处理的节点) < len(self.节点集合):
            零入度节点 = []
            for 节点 in self.节点集合:
                if 节点 not in 已处理的节点 and 当前入度[节点] == 0:
                    零入度节点.append((self.节点优先级[节点], 节点))
            
            if not 零入度节点 and len(已处理的节点) < len(self.节点集合):
                return "错误：场景中存在循环依赖，无法生成有效的攻击步骤序列"
            
            零入度节点.sort(key=lambda x: -x[0])
            
            for 节点优先级, 当前节点 in 零入度节点:
                已处理的节点.add(当前节点)
                
                出边 = []
                for 邻居 in self.图[当前节点]:
                    边 = (当前节点, 邻居)
                    if 边 not in 已处理的边:
                        组合优先级 = self.边到权重[边] + self.节点优先级[邻居]
                        出边.append((组合优先级, self.边到权重[边], 邻居, 边))
                
                出边.sort(key=lambda x: (-x[0], -x[1]))
                
                for 组合优先级, 边权重, 邻居, 边 in 出边:
                    步骤序列.append((len(步骤序列) + 1, self.边到步骤[边], 当前节点, 邻居, 边权重, self.节点优先级[邻居]))
                    已处理的边.add(边)
                    
                    当前入度[邻居] -= 1
        
        return 步骤序列
    
    def 打印攻击步骤(self):
        """打印生成的攻击步骤序列，包含节点优先级信息"""
        步骤序列 = self.生成攻击步骤()
        
        if isinstance(步骤序列, str):
            print(步骤序列)
            return
        
        print("\n===== 攻击步骤序列 =====")
        for 序号, 描述, 源, 目标, 边权重, 节点优先级 in 步骤序列:
            print(f"步骤 {序号}: {描述} (从 {源} 到 {目标}) [边权重: {边权重}, 目标节点优先级: {节点优先级}]")
        print("=====================\n")

# 演示程序
def 主程序():
    print("按照提示输入设备之间的连接关系、边权重和节点优先级，输入'完成'结束输入。\n")
    
    系统 = 场景战术系统()
    
    print("==== 阶段1：输入连接关系和边权重 ====")
    while True:
        输入内容 = input("输入连接 (格式: 源设备 目标设备 边权重)，或输入'下一步'进入节点优先级设置: ")
        
        if 输入内容.lower() in ['下一步', 'next']:
            break
            
        try:
            部分 = 输入内容.split()
            if len(部分) < 2 or len(部分) > 3:
                print("输入格式错误！请使用 '源设备 目标设备 [边权重]' 的格式。")
                continue
                
            源设备 = 部分[0]
            目标设备 = 部分[1]
            边权重 = int(部分[2]) if len(部分) == 3 else 0
            
            系统.添加连接(源设备, 目标设备, 边权重)
            print(f"已添加连接: {源设备} -> {目标设备} [边权重: {边权重}]")
            
        except Exception as e:
            print(f"发生错误: {e}")
    
    print("\n==== 阶段2：设置节点优先级 ====")
    print("现有节点: " + ", ".join(系统.节点集合))
    
    while True:
        输入内容 = input("请输入节点优先级 (格式: 设备 优先级)，或输入'完成'结束输入: ")
        
        if 输入内容.lower() == '完成':
            break
            
        try:
            部分 = 输入内容.split()
            if len(部分) != 2:
                print("输入格式错误！请使用 '设备 优先级' 的格式。")
                continue
                
            设备 = 部分[0]
            优先级 = int(部分[1])
            
            if 设备 not in 系统.节点集合:
                print(f"错误：设备 '{设备}' 不存在！")
                continue
                
            系统.设置节点优先级(设备, 优先级)
            print(f"已设置节点优先级: {设备} [优先级: {优先级}]")
            
        except Exception as e:
            print(f"发生错误: {e}")
    
    系统.打印攻击步骤()
    
if __name__ == "__main__":
    主程序()